package LeetCode.interview;

import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;




import javafx.scene.transform.Rotate;

import com.sun.xml.internal.messaging.saaj.packaging.mime.Header;

import util.LogUtils;
import util.datastructure.ListNode;
import util.datastructure.TreeNode;

/*
 * 
原题

　　Given an array where elements are sorted in ascending order, convert it to a height balanced BST. 

题目大意

　　给定一个升序排列的二叉树，将其转换为一棵高度平衡的二叉树。 

解题思路
这道题是要求把有序链表转为二叉搜索树，和之前那道Convert Sorted Array to Binary Search Tree 将有序数组转为二叉搜索树思路完全一样，只不过是操作的数据类型有所差别，一个是数组，一个是链表。数组方便就方便在可以通过index直接访问任意一个元素，而链表不行。由于二分查找法每次需要找到中点，而链表的查找中间点可以通过快慢指针来操作，可参见之前的两篇博客Reorder List 链表重排序和Linked List Cycle II 单链表中的环之二有关快慢指针的应用。找到中点后，要以中点的值建立一个数的根节点，然后需要把原链表断开，分为前后两个链表，都不能包含原中节点，然后再分别对这两个链表递归调用原函数，分别连上左右子节点即可。代码如下：
   @TODO:再思考下
 * @Date 2017-10-03 23：28
 */
public class _108_Convert_Sorted_Array_to_Binary_Search_Tree {
	


    public TreeNode sortedListToBST(ListNode head) {
    	if (head == null)	return null;						//子节点
    	if (head.next == null)	return new TreeNode(head.val);
    	ListNode fast = head, slow = head, last = slow;
    	while (fast.next!=null && fast.next.next!=null) {
    		last = slow;
    		fast = fast.next.next;
    		slow = slow.next;
    	}
    	ListNode r = slow.next;
    	last.next = null;
    	TreeNode root = new TreeNode(slow.val);
    	if (slow != head) 
    		root.left  = sortedListToBST(head);
    	root.right = sortedListToBST(r);
    	return root;
    }
    
    /**
     * 发现链表中间节点
     * @param head
     */
    private ListNode findMid(ListNode head) {
    	if (head == null)	return null;
    	ListNode fast = head, slow = head;
    	while (fast.next!=null && fast.next.next!=null) {
    		fast = fast.next.next;
    		slow = slow.next;
    	}
    	return slow;
    }
	
	public static void main(String[] args) {
		_108_Convert_Sorted_Array_to_Binary_Search_Tree obj = new _108_Convert_Sorted_Array_to_Binary_Search_Tree();
		LogUtils.println("结果", 
				obj.sortedListToBST(
						ListNode.newLinkListOrdered()
				));
	}
}
